Greg Detre
@14:30 on Monday, September 23, 2002
uninformed
search
state, actions, goal test, path cost
8-puzzle
easier to think about actions as moving the space (rather than the tiles)???
8-puzzle has 181440 states, 15-puzzle has 1.3 trillion (solve in about a millesecond), 24-puzzle has 1025
giga���� 109������������������ quintillion�???
tera����� 1012
peta���� 1015
exa������ 1018
8 queens problem
constraint-satisfaction � position 8 queens on a chessboard without any of them being able to attack another
the number of states depends on how you define the problem
if you define the state as 0�8 queens such that no queens are attacking each other � a valid action is to place a queen in the left-most column s.t. it is not attacked by any other queen
somewhere between 8! and cube-root of 8!
romanian roads problem
uninformed search
search tree � closed nodes (already checked), open nodes (yet to be checked)
distinguish between node in the search tree itself and a state in the problem domain
a node in the search tree will represent a state in the problem domain, but it will contain much more information (e.g. how you got there), and so there will be more nodes in the search tree than states in the problem domain
depth � how many levels down the search tree did you have to go to get to that depth
path cost � total cost to get to a given node
frontier � all the nodes that are currently open
performance metrics
a complete algorithm (always finds a solution if a solution exists), vs an optimal algorithm (finds the minimum path solution)
b branching factor � number of children of a given node
d solution depth (to optimal solution)
m maximum length of a path
time � total number of nodes � in total, over the whole algorithm
space�� maximum number of nodes (in queue, at any one time)
in uninformed search, we can only distinguish goal states from non-goal states, and generate successors
vs informed search, where we have heuristics and �
search algorithm
check whether we�re at the goal
get the children, add them to the queue
check the next in the queue
uniform cost � depth first, grow by the cost
BFS
complete and optimal
space gets to be a problem first, quite often
Walmart has 12Tb of data, apparently
DFS time complexity O(bm) � the textbook is wrong if it says O(bd)
exponential time complexity but good space complexity
if we know a bit more about the problem, then you can simply capth the maximum depth
diameter of the search space � maximum number of actions to get from the initial state to any other state
requires you to know which state is furthest
iterative deepening search
visits new nodes in the same order as BFS
but it drastically cuts down the space requirements (because you�re not maintaining the whole frontier in space)
it can involve revisiting nodes though
don�t understand the cheaper-than-BFS solution he considers next� (magic � IDS is faster)???
bi-directional search
also search back from the goal state
reduces time complexity from bd to 2bd/2
best case is when the branching factor is symmetric in the forward/reverse directions (e.g. from 11m to 22,000)
requires you to know more about where your goal is, i.e. enumerate goals rather than just a T/F goal test
assume that your actions can go backwards/don�t lose information, i.e. the reverse operator might have a very large branching factor (e.g. predecessors to a checkmate state)
you have a problem checking when your start-forwards and goal-reverse states meet
this creates a space problem
if you want to do a fast comparison (O(k), i.e. constant time look-up) between your two directional searches, then a hash table takes a lot of space
so you could have a trade-off, which takes less space, but won�t be so fast checking
you can also try and only maintain the interesting parts of the frontier
avoiding repeated states
�any algorithm that forgets history is doomed to repeat it� � AIMA
it doesn�t take much memory to be sure that you never revisit a parent/ancestor node (will only avoid infinite loops), but it takes much more memory to remember all the states you�ve visited (but this still isn�t as bad as BFS, because you don�t have to remember the nodes, just the states (i.e. the cities, not the routes to get there)
reading: AIMA 1,2,3,4-4.3
data-mining project, paid
Michael Kearns � Monday 30th Sept, 4pm, New models and algorithms for computational game theory � MD G125
filll in section sheet